//kmp
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>

void GetNext(char *s2,int *next)
{
	int len=strlen(s2);
	next[0]=-1;
	int i=0,j=-1;
	while(i<len-1)
	{
		if(j==-1 || s2[i]==s2[j])
		{
			++i;++j;next[i]=j;
		}else
			j=next[j];
	}
}
int kmp(char *s1,char *s2)
{
	int i=0,j=0;
	int len1=strlen(s1);
	int len2=strlen(s2);
	int *next=(int *)malloc(sizeof(int)*len2);
	GetNext(s2,next);
	while(i<len1 && j<len2)
	{
		if(j==-1 || s1[i]==s2[j])
		{
			i++;j++;
		}
		else
			j=next[j];
	}
	if(j==len2)
		return i-len2;
	else
		return -1;
}
void main()
{
	char *s1="aaaaab";
	char *s2="aab";
	int num=kmp(s1,s2);
	printf("%d\n",num);
}